/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：MergeSort.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-06
Function List ：
Description   ：Merge Sort
******************************************************/

#include "MergeSort.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"

// Static Function Lists
void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right);
void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd);

void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd) {
    int i;
    int LeftEnd;
    int NumElements;
    int TmpPos;

    LeftEnd = Rpos - 1;
    TmpPos = Lpos;
    NumElements = RightEnd - Lpos + 1;

    /* main loop */
    while (Lpos <= LeftEnd && Rpos <= RightEnd) {
        if (A[Lpos] <= A[Rpos]) {
            TmpArray[TmpPos++] = A[Lpos++];
        } else {
            TmpArray[TmpPos++] = A[Rpos++];
        }
    }

    /* Copy rest of first half */
    while (Lpos <= LeftEnd) {
        TmpArray[TmpPos++] = A[Lpos++];
    }

    /* Copy rest of second half */
    while (Rpos <= RightEnd) {
        TmpArray[TmpPos++] = A[Rpos++];
    }

    /* Copy TmpArray back */
    for (i = 0; i < NumElements; ++i, --RightEnd) {
        A[RightEnd] = TmpArray[RightEnd];
    }
}

void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right) {
    int Center;

    if (Left < Right) {
        Center = (Left + Right) / 2;
        MSort(A, TmpArray, Left, Center);
        MSort(A, TmpArray, Center + 1, Right);
        Merge(A, TmpArray, Left, Center + 1, Right);
    }
}

void MergeSort(ElementType A[], int N) {
    ElementType *TmpArray;

    TmpArray = (ElementType *)malloc(N * sizeof(ElementType));
    if (TmpArray != NULL) {
        MSort(A, TmpArray, 0, N - 1);
        free(TmpArray);
    } else {
        FatalError("No space for tmp array!!!");
    }
}

// EOF

